class Solution(object):
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        deque = []
        ret = []
        for i, num in enumerate(nums):
            while deque and deque[0]<=i-k:
                deque.pop(0)
            while deque and nums[deque[-1]]<=num:
                deque.pop()
            deque.append(i)
            if i>=k-1:
                ret.append(nums[deque[0]])
        return ret

print(Solution().maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3))